package com.twq.types.typeparam.upperbound

import scala.annotation.tailrec

/**
 * Created by tangweiqun on 2017/12/1.
 * Upper Bound
 * Lower Bound
 */
trait MyOrder[T] {
  def compare(that: T): Int

  def <(that: T): Boolean = (this compare that) < 0

  def >(that: T): Boolean = (this compare that) > 0

  def <=(that: T): Boolean = (this compare that) <= 0

  def >=(that: T): Boolean = (this compare that) >= 0
}

class Person(val firstName: String, val lastName: String) extends MyOrder[Person] {
  def compare(that: Person) = {
    val lastNameComparison =
      lastName.compareToIgnoreCase(that.lastName)
    if (lastNameComparison != 0)
      lastNameComparison
    else
      firstName.compareToIgnoreCase(that.firstName)
  }

  override def toString = firstName + " " + lastName
}

object UpperBound {
  //表明类型参数T必须要有一个父类MyOrder[T]
  //上界：类型参数必须是MyOrder[T]类型或者是MyOrder[T]的子类，MyOrder[T]我们称之为上界
  def orderedMergeSort[T <: MyOrder[T]](xs: List[T]): List[T] = {
    def merge(xs: List[T], ys: List[T]): List[T] =
      (xs, ys) match {
        case (Nil, _) => ys
        case (_, Nil) => xs
        case (x :: xs1, y :: ys1) =>
          if (x < y) x :: merge(xs1, ys)
          else y :: merge(xs, ys1)
      }

    val n = xs.length / 2
    if (n == 0) xs
    else {
      val (ys, zs) = xs splitAt n
      merge(orderedMergeSort(ys), orderedMergeSort(zs))
    }
  }

  def main(args: Array[String]): Unit = {
    val people = List(
      new Person("Larry", "Wall"),
      new Person("Anders", "Hejlsberg"),
      new Person("Guido", "van Rossum"),
      new Person("Alan", "Kay"),
      new Person("Yukihiro", "Matsumoto")
    )

    val sortedPeople = orderedMergeSort(people)
    println(sortedPeople)

    //val wontCompile = orderedMergeSort(List(3, 2, 1))
  }
}
